package test.algorithm;

import org.junit.Test;

/**
 * 迷宫游戏
 * 
 * @author 延晓磊
 *
 * @since 2020年7月3日
 */
public class MazeGame {

	@Test
	public void test() {
		// 绘制迷宫
		int[][] maze = creaetMaze();
		// 寻路：迷宫，起点，终点
		System.out.println(findWay(maze, 2,1, 6,6) ? "已走到终点 Y(^_^)Y" : "未走到终点 ::>_<::");
		// 打印迷宫路线
		print(maze);
	}

	/**
	 * 绘制迷宫
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月3日
	 */
	public static int[][] creaetMaze() {
		// 迷宫
		int[][] maze = new int[8][8];
		// 墙-列：1
		for (int i = 0; i < 8; i++) {
			maze[i][0] = 1;
			maze[i][7] = 1;
		}
		// 墙-行：1
		for (int i = 1; i < 7; i++) {
			maze[0][i] = 1;
			maze[7][i] = 1;
		}
		// 墙-档板：1
		maze[3][1] = 1;
		maze[3][2] = 1;
		return maze;
	}
	
	/**
	 * 寻路，按照"下>右>上>左"的优先策略
	 * 
	 * @param maze		迷宫
	 * @param startI	起点
	 * @param startJ
	 * @param endI		终点
	 * @param endJ
	 * 
	 * @return 是否通行
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月3日
	 */
	public static boolean findWay(int[][] maze, int startI, int startJ, int endI, int endJ) {
		if (maze[endI][endJ] == 2) {
			// 递归出口：探测到终点
			return true;
		}else {
			// 未探测
			if (maze[startI][startJ] == 0) {
				// 探测
				maze[startI][startJ] = 2;
				// 下一步：递归回朔
				if (findWay(maze, startI + 1, startJ, endI, endJ)) {
					// 向下
					return true;
				}else if (findWay(maze, startI, startJ + 1, endI, endJ)) {
					// 向右
					return true;
				}else if (findWay(maze, startI - 1, startJ, endI, endJ)) {
					// 向上
					return true;
				}else if (findWay(maze, startI, startJ - 1, endI, endJ)) {
					// 向左
					return true;
				}else {
					// 路线不通
					maze[startI][startJ] = 3;
					return false;
				}
			}else {
				// 墙、已探测
				return false;
			}
		}
	}
	
	/**
	 * 打印迷宫
	 * 
	 * @param maze	迷宫
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月3日
	 */
	public static void print(int[][] maze) {
		// 行
		for (int i = 0; i < 8; i++) {
			// 列
			for (int j = 0; j < 8; j++) {
				System.out.print(maze[i][j] + " ");
			} 
			System.out.println();
		} 
	}

}
